Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.
If there is no common time slot that satisfies the requirements, return an empty array.
The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.
It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.
Example 1:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8 Output: [60,68]
Example 2:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12 Output: []
Constraints:
1 <= slots1.length, slots2.length <= 104slots1[i].length, slots2[i].length == 2slots1[i][0] < slots1[i][1]slots2[i][0] < slots2[i][1]0 <= slots1[i][j], slots2[i][j] <= 1091 <= duration <= 106
Average Rating: 5.00 (15 votes)
Solution
Overview
To find the earliest time slot that works for both the people, the most straightforward approach would be to examine all possible time slots for them. To improve it, we can either sort both input arrays and apply two pointers, or we can use a heap for sorting the time slots and find the earliest overlapping time slot. We will cover both of these approaches in this article.
Approach 1: Two pointers
Intuition
Figure 1. The common slot between two slots.
We want to sort both slots1 and slots2 by the start time first, then initialize two pointers, each of which points to the beginning of the two arrays. From there, we will compare the two slots, and move one pointer at a time if the common slot is smaller than duration.
Note that sorting by the start time vs the end time is the same, this is because, if a time slot starts earlier, it will end earlier. Remember that for both people, there're no overlapping time slots
Here comes the question: how do we decide which pointer should be incremented?
The answer is: we will always move the one that ends earlier. Assuming that we are comparing slots1[i] and slots2[j] and slots1[i][1] > slots2[j][1], we would always choose to move the pointer j. The reason is that, as both slots are sorted, if slots1[i][1] > slots2[j][1], we know slots1[i+1][0] > slots2[j][1] so that there will be no intersection between slots1[i+1] and slots2[j].
Figure 2. Always move the one that ends earlier.
Algorithm
- Sort both
slots1andslots2by the start time. - Initialize two pointers,
pointer1andpointer2, pointing to the beginning ofslots1and the beginning ofslots2respectively. - Iterate until
pointer1reaches the end ofslots1orpointer2reaches the end ofslots2:- Find the common slot of
slots1[pointer1]andslots2[pointer2]. - If the common slot is greater than or equal to
duration, return the result. - Else, find the slot that ends earlier and move the pointer.
- Find the common slot of
- If no common slot is found, return an empty array.
Implementation
Complexity Analysis
-
Time complexity: O(MlogM+NlogN), when M is the length of
slots1and N is the length ofslots2.Sorting both arrays would take O(MlogM+NlogN). The two pointers take O(M+N) because, during each iteration, we would visit a new element, and there are a total of M+N elements. Putting these together, the total time complexity is O(MlogM+NlogN).
-
Space complexity: O(1). This is because we do not use any additional data structures; we only use a few fixed-size integer variables.
Approach 2: Heap
Intuition
Another approach of systematically selecting slots and comparing them is using a heap. We would initialize a heap timeslots and push all of the time slots into it.
The key idea here is that we only need one heap. That is, we can put the time slots for both people into the same heap, and then if we find a common time slot, we know that the two-time slots couldn't possibly be for the same person. Before reading the justification for this, have a think for yourself about why we can draw such a bold conclusion.
The problem description states that the time slots for a single person do not overlap. This means that if, for example, we have the time slots [10, 15] and [14, 20], then we know that these time slots cannot be for the same person. Otherwise, we would have a contradiction. So, given that a common time slot has to overlap, the two slots have to be from different people.
A heap returns the smallest items first. Because of this time slots we remove from the heap are sorted by the start time. Taking advantage of this, we can then compare the time slots in the order of time.
Figure 3. Compare the popped time slot and the top element in the heap.
Algorithm
- Initialize a heap
timeslotsand push time slots that last longer thandurationinto it. - Iterate until there's only one time slot remaining in
timeslots:- Pop the first time slot
[start1, end1]fromtimeslots. - Retrieve the next time slot
[start2, end2], which is the current top element intimeslots. - If we find
end1 >= start2 + duration, becausestart1 <= start2, the common slot is longer thandurationand we can return it.
- Pop the first time slot
- If we don't find the common slot that is longer than
duration, return an empty array.
Implementation
Complexity Analysis
-
Time complexity: O((M+N)log(M+N)), when M is the length of
slots1and N is the length ofslots2.There are two parts to be analyzed: 1) building up the heap; 2) the iteration when we keep popping elements from the heap. For the second part, popping one element takes O(log(M+N)), therefore, in the worst case, popping M+N elements takes O((M+N)log(M+N)).
Regarding the first part, we have different answers for Java and Python implementations. For Python,
heapq.heapifytransforms a list into a heap, in-place, in linear time; however, in Java, we choose to pop each element into the heap, which leads to a time complexity of O((M+N)log(M+N)). Note that it is possible to convert the array into a heap in linear time using the constructor ofPriorityQueue; however, that will not influence the overall time complexity and will make it less readable.When we put these two parts together, the total time complexity is O((M+N)log(M+N)), which is determined by the first part.
-
Space complexity: O(M+N). This is because we store all M+N time slots in a heap.
Last Edit: February 19, 2021 7:48 PM
Thank you for the solutions! I liked the first approach.
Two pointer approach in Javascript:
var minAvailableDuration = function(slots1, slots2, duration) {
slots1.sort((a, b) => a[0] - b[0]);
slots2.sort((a, b) => a[0] - b[0]);
let pointer1 = 0,
pointer2 = 0;
while (pointer1 < slots1.length && pointer2 < slots2.length) {
let intersectStart = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
let intersectEnd = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
if (intersectStart + duration <= intersectEnd) {
return [intersectStart, intersectStart + duration];
} else if (slots1[pointer1][1] < slots2[pointer2][1]) {
pointer1++;
} else {
pointer2++;
}
}
return [];
};
In the explanation for Solution 2 I believe start1<start2 (technically start1<=start2) since this is a min heap. Please let me know if you think otherwise.
May 25, 2021 12:35 AM
if someone comes up with second approach in interview, that would be extra bonus to come up such smart solution. Really nice solution the second one. First one was kind of conventional way one could approach after having practiced 2 pointers.
Sweeping the time line easily understandable solution (O(nlogn)) using an ordered map.
class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
// sweep the timeline
map<int, int> avail;
for (auto slot: slots1){
avail[slot[0]]++;
avail[slot[1]]--;
}
for (auto slot: slots2){
avail[slot[0]]++;
avail[slot[1]]--;
}
int present=0;
vector<int> answer (2);
for (auto pair: avail){
present+=pair.second;
if (present==2){
answer[0]=pair.first;
}
else if (present==0 && pair.second==-2 && pair.first-answer[0]>=duration){// if both become busy
answer[1]=answer[0]+duration;
return answer;
}
else if (present==1 && pair.second==-1 && pair.first-answer[0]>=duration){// if one of them becomes busy after both being free
answer[1]=answer[0]+duration;
return answer;
}
}
return {};
}
};
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) { }};


